1. Field of the Invention
The present invention relates to computer hardware and software, and more particularly to a system for thread synchronization in a distributed computing environment wherein multiple threads of execution span across different computing platforms.
2. Description of the Prior Art
The logical progression of executed steps in a microprocessor is called a xe2x80x9cthreadxe2x80x9d of execution. Simple computer systems have a single microprocessor and an operating system that allows only one active thread of execution. Thus, software will execute in a serial fashion, with each operation running sequentially after the termination of the previous operation. This type of operating system becomes inefficient when system resources halt to allow a long calculation to finish executing.
For example, suppose that certain calculations were being performed on batches of data that were input by a data entry operator. In a system with a single thread of execution, the data entry operator would have to pause while each calculation was finished on the previous batch of data. It would be more efficient if the data entry operator could continuously input the data while calculations on the previous batch of data were executing in the background. Such a system would require multiple threads of execution: a first thread to process the input from the operator, and a second thread to perform the calculations on the previous batch of data.
In the example above, a multithreading scheme would be fairly simple to devise because it is unlikely that the first and second threads would interfere with each other. Each thread would execute on its own stack independently of the other. This is often called xe2x80x9cunsynchronizedxe2x80x9d multithreading.
In a computer with a single microprocessor, unsynchronized multithreading may be accomplished by time-multiplexing the microprocessor. This means that the microprocessor, or CPU, divides its time between two or more stacks such that all stacks make some progress over time, without having the stacks explicitly call each other. The first stack would wait while execution proceeded on the second stack, and vice versa. As used herein, the term xe2x80x9cconcurrent threadsxe2x80x9d means that two or more threads are in various stages of execution concurrently. Concurrent threads may be executing one at a time in a time multiplexing scheme. Alternatively, a computer with parallel processors may have concurrent threads executing simultaneously.
There are a number of known techniques for time-multiplexing, including xe2x80x9cpreemptivexe2x80x9d and xe2x80x9cnon-preemptivexe2x80x9d multitasking. In a preemptive multitasking scheme, the operating system allocates time among the threads. In a non-preemptive scheme, the active thread controls the time at which it relinquishes execution.
In general, there is no assurance that multiple threads of execution can run concurrently without interfering with each other. For example, two threads of execution may access the same location in memory to store intermediate results. In this scenario, the first thread may store a value to memory, followed by the second thread over-writing a different value to the same location in memory. Thus, when the first thread retrieves the value it will corrupt the calculation in unpredictable ways. Resources that may be shared among concurrent threads, such as memory, must be protected in a manner that prevents corruption between the threads.
The process of assuring that concurrent threads do not interfere with each other is called xe2x80x9cthread synchronization.xe2x80x9d Modern operating systems that allow multitasking operations have various tools to accomplish thread synchronization. Some examples include locks, monitors, and request servers.
Locks are relatively simple programming constructs that protect shared resources. A lock must be xe2x80x9cacquiredxe2x80x9d by a thread of execution before that thread can access the shared resource. Prior to gaining control of the shared resource, the thread must show evidence that it has acquired the lock, or alternatively, the entire system must respect a convention in which threads without locks refrain from accessing the shared resource. In a simple system, the shared resource may only allow one lock to issue at any time, thus preventing any concurrent access to the resource.
Locks can be difficult to use in a layered or nested architecture because the lock evidence must be explicitly supplied to allow access to the shared resource. This presents a problem when a first thread acquires a lock, then waits for results from a second thread which also needs access to the same resource. This scenario can lead to a xe2x80x9cdeadlockxe2x80x9d in which the first and second threads are each waiting for the other, as described in the following example:
Suppose a method or procedure called xe2x80x9cfoo( )xe2x80x9d acquires a lock on resource xe2x80x9cR.xe2x80x9d Subsequently, xe2x80x9cfoo( )xe2x80x9d calls xe2x80x9cgoo( )xe2x80x9d which also tries to acquire a lock on the resource R. The attempt by xe2x80x9cgoo( )xe2x80x9d to acquire the lock will fail even though xe2x80x9cgoo( )xe2x80x9d is operating on behalf of xe2x80x9cfoo( ).xe2x80x9d Thus, even when method xe2x80x9cfoo( ).xe2x80x9d has a lock, it can deadlock a system by calling a second method xe2x80x9cgoo( )xe2x80x9d if both methods need the same resource R. A higher level concept, called a xe2x80x9cmonitor,xe2x80x9d provides a solution to this type of nesting problem.
Local xe2x80x9cmonitorsxe2x80x9d are a well known technique for thread synchronization. They are fairly easy to use and map well to object-oriented systems. In certain respects, a local monitor can be viewed as a programming construct in which a lock is assigned to a thread. In contrast, a simple lock (as described in the example above) is typically assigned to a shared resource. The local monitor is associated with the thread""s section of code in which shared access is performed. Each local monitor comprises a queue and a lock. As a thread proceeds into a monitor, the thread will either be assigned a spot on the queue, or will be granted access to the resource while other threads wait on the queue. In this manner, a lock does not have to be passed from thread to thread.
Another technique for thread synchronization involves a xe2x80x9crequest server.xe2x80x9d A separate computing platform constitutes the request server, and clients to this server are the individual threads of execution. The server creates individual (local) threads of execution to handle each request from a client. Thus, the problems associated with distributed system concurrency control are reduced to a local problem of concurrency control where well known techniques can be applied. One of the drawbacks of this approach is the large overhead required to generate a new thread for each client request.
Several U.S. Patents are directed to the problem of thread synchronization. For example, U.S. Pat. No. 5,341,491 discloses an apparatus and method for ensuring that lock requests are serviced in a multiprocessor system. According to the disclosure, a lock queue includes a plurality of registers pipelined together, wherein lock requests only enter the lock queue if they are refused access to a shared resource a predetermined number of times.
U.S. Pat. Nos. 5,636,376 and 5,675,798 disclose a system and method for selectively and contemporaneously monitoring processes in a multiprocessing server. A status utility selectively accesses information to determine the status of the individual multiple processes executing on the server workstation. The information is of a granularity to identify processes which are hung up on semaphores, message queues, or the like.
U.S. Pat. No. 5,590,335 discloses a process for analysis of deadlocks in an operating system. The process includes the step of searching for any thread stopped on a lock, and further for the thread that holds that lock, and further up the chain until a cycle is found. In this manner, the user can reconstruct the cycle determining the deadlock.
U.S. Pat. No. 5,590,326 discloses a shard data management scheme using shared data locks for multi-threading. In this scheme, different shared data identifiers are assigned to different threads, and different locks are set up for different shared data identifiers, so as to enable the detection of an access in violation to the locks.
U.S. Pat. No. 5,524,247 discloses a system for scheduling programming units to a resource based on status variables indicating a lock or lock-wait state. The central processing unit (CPU) sets a predetermined value in the status variable corresponding to a thread when the thread starts waiting for a resource which it shares with other threads. The scheduler refers to the status variable, selects, with priority, a thread other than the thread waiting for the shared resource, and allocates the CPU to the thread thus selected.
U.S. Pat. No. 5,706,515 discloses a system for implementing an atomic wait for notification operations. A resource allocation subsystem includes an xe2x80x9cinitializationxe2x80x9d procedure for initializing monitors, a xe2x80x9cnotifyxe2x80x9d procedure and a xe2x80x9cwaitxe2x80x9d procedure. Each monitor has an associated event data structure denoting the status of the monitor as Signaled or Unsignaled. Each monitor also stores a value indicating how many threads are waiting on the monitor.
U.S. Pat. No. 5,247,675 discloses preemptive and non-preemptive scheduling and execution of program threads in a multitasking operating system. The operating system permits application programs to influence the schedule of execution of program threads. A priority level is assigned to each thread, and the highest priority thread is executed first.
U.S. Pat. No. 5,481,706 discloses a system and method for creating thread-safe shared libraries. The system insures correct functioning and integrity of the library functions accessible by multiple threads. A write-exclusive lock is used to protect shared resources.
Computer networks can allow different computing platforms to exchange data and to share network resources and peripheral devices. In simple computer networks, software will only execute within a single platform, although data may be accessed from various resources within the network. The issues surrounding thread synchronization typically remain local to each computing platform.
More recent developments in computer networking have enabled the execution of threads to progress across several different computing platforms. A xe2x80x9cthread jumpxe2x80x9d occurs when a thread is executing on a first computing platform, and subsequently continues its execution on a second computing platform within the network. Networks of computing platforms that allow thread jumps are herein referred to a xe2x80x9cdistributed systems.xe2x80x9d
The problem of thread synchronization presents itself anew with distributed systems. The advent of thread jumps typically requires a method of thread synchronization that applies throughout the network. Prior synchronization systems are not normally applicable because they apply within the confines of a single computing platform. What has been desired, and is addressed by the by present invention is a system and method for thread synchronization that applies to distributed systems.
The present invention extends the applicability of monitors to distributed systems. An important element of the present invention is the xe2x80x9clogical threadxe2x80x9d which is comprised of one or more xe2x80x9clocal threads.xe2x80x9d While a local thread exists within a single computing platform, a logical thread may span several local threads, and thereby span the platforms on which the local threads reside. For example, in an object-oriented system, if an object on machine A makes a method call on an object on machine B, local threads on each machine (the calling thread and the called thread) belong to the same logical thread of execution. Thus, according to the present invention, monitors may be adapted to work with logical threads.
A mapping exists within each computing platform which maps local threads to logical threads. The mapping may be in the form of a hash table, or any other programming construct which associates local threads with logical threads. As new local threads are spawned by calls from other parts of the network, the new local threads are assigned to logical threads by the mapping construct.
Monitors within each platform are designed to function with logical threads instead of local threads. When a local thread enters a monitor, access to the shared resource is determined on the basis of the logical thread to which the local thread is affiliated. Thus, if the calling thread on a first machine has already gained access to a monitor, the called thread on a second machine will not be precluded from accessing the same resource.